/**
 * https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
 var lowestCommonAncestor = function(root, p, q) {
  let result = null;
  function hasPorQ(node) {
      if (!node) {
          return false;
      }
      const l = hasPorQ(node.left);
      const r = hasPorQ(node.right);
      // pq在两边
      if (l && r) {
          if (result === null) {
              result = node;
          }
          return true;
      }
      // pq在同一边
      if (l || r) {
          if ((node === p || node === q) && result === null) {
              result = node;
          }
          return true;
      }
      return node === p || node === q;
  }
  hasPorQ(root, null);
  return result;
};